//N 皇后
/*按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 1 <= n <= 9*/
 class Solution {
    bool col[10] = {0};
    bool dig1[19] = {0};
    bool dig2[19] = {0};
    vector<string> path;
    vector<vector<string>> ret;

public:
    vector<vector<string>> solveNQueens(int n) {
        string s(n,'.');
        dfs(s, n, 0);
        return ret;
    }
    void dfs(string& s, int& n, int pos) {
        if (path.size() == n) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (col[i] == false && dig1[pos - i + n] == false &&
                dig2[i + pos] == false) {
                path.push_back(s);
                path[pos][i] = 'Q';
                col[i] = true;
                dig1[pos - i + n] = true;
                dig2[i + pos] = true;
                dfs(s, n, pos + 1);
                path.pop_back();
                col[i] = false;
                dig1[pos - i + n] = false;
                dig2[i + pos] = false;
            }
        }
    }
};

//优化版本
class Solution {
    bool col[10] = {0};
    bool dig1[19] = {0};
    bool dig2[19] = {0};
    vector<string> path;
    vector<vector<string>> ret;
    int count = 0;

public:
    vector<vector<string>> solveNQueens(int n) {
        // string s(n,'.');
        // dfs(s, n, 0);
        string s(n, '.');
        for (int i = 0; i < n; i++) {
            path.push_back(s);
        }
        dfs(n, 0);
        return ret;
    }
    // void dfs(string& s, int& n, int pos)
    void dfs(int& n, int pos) {
        // if (path.size() == n)
        if (count == n) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (col[i] == false && dig1[pos - i + n] == false &&
                dig2[i + pos] == false) {
                // path.push_back(s);
                path[pos][i] = 'Q';
                col[i] = true;
                dig1[pos - i + n] = true;
                dig2[i + pos] = true;
                count++;
                //dfs(s, n, pos + 1);
                dfs(n, pos + 1);
                // path.pop_back();
                path[pos][i] = '.';
                col[i] = false;
                dig1[pos - i + n] = false;
                dig2[i + pos] = false;
                count--;
            }
        }
    }
};